package main

import (
	"fmt"
)

/*
稀疏图 - 邻接表
时间复杂度：
优点：
缺点：

*/


type sparseGraph struct {
	n int
	m int
	directed bool
	g [][]int
}

func (sg *sparseGraph) init(n int, directed bool) {
	sg.n = n
	sg.m = 0
	sg.directed = false

	sg.g = make([][]int, n)
	//for i := range dg.g {
	//	dg.g[i] = make([]bool, n)
	//}
}

func (sg *sparseGraph) V() int {
	return sg.n
}

func (sg *sparseGraph) E() int {
	return sg.m
}

func (sg *sparseGraph) addEdge(v int, w int) {

	sg.g[v] = append(sg.g[v], w)

	if v != w && sg.directed {
		sg.g[w] = append(sg.g[w], v)
	}

	sg.m++
}

func (sg *sparseGraph) show() {

	for i, v := range sg.g {
		fmt.Println(i, " " , v)
	}
}

var componentCount int
var visited []bool
var id []int

func (sg *sparseGraph) getComponentCount() int {

	componentCount = 0
	visited = make([]bool, sg.n)

	for i := 0; i < sg.n; i++{
		id = append(id, -1)
	}

	for i, v := range sg.g {

		fmt.Println(i, v)
		if visited[i] {
			continue
		}

		sg.dfs(i)
		componentCount++
	}

	return componentCount
}

// 深度优先遍历  邻接表：O(V + E) 邻接矩阵：O(V2)
func (sg *sparseGraph) dfs(i int) {

	visited[i] = true
	id[i] = componentCount

	for _, x := range sg.g[i] {

		if !visited[x] {
			sg.dfs(x)
		}
	}
}

var from []int
func (sg *sparseGraph) initPath(source int) {

	visited = make([]bool, sg.n)

	for i := 0; i < sg.n; i++ {
		from = append(from, -1)
	}

	sg.dfsPath(source)

}


func (sg *sparseGraph) dfsPath(i int) {

	visited[i] = true

	for _, x := range sg.g[i] {
		fmt.Println(i , x,  sg.g[i])
		if !visited[x] {
			from[x] = i
			sg.dfsPath(x)
		}
	}
}

func (sg *sparseGraph) hasPath(w int) bool {

	return visited[w]

}

func (sg *sparseGraph) showPath(w int) {

	stack := make([]int, 0)

	p := from[w]
	for p != -1 {
		stack = append(stack, p)
		p = from[p]
	}

	for i := len(stack)-1; i >= 0; i-- {
		fmt.Println("=>", stack[i])
	}

}

func (sg *sparseGraph) isConnected(v int, w int) bool {
	return id[v] == id[w];
}



func main()  {

	//data := [][]int {
	//	{13, 13},
	//	{0, 5},
	//	{4, 3},
	//	{0, 1},
	//	{9, 12},
	//	{6, 4},
	//	{5, 4},
	//	{0, 2},
	//	{11, 12},
	//	{9, 10},
	//	{0, 6},
	//	{7, 8},
	//	{9, 11},
	//	{5, 3},
	//
	//}

	data := [][]int {
		{6, 8},
		{0, 1},
		{0, 2},
		{0, 5},
		{1, 2},
		{1, 3},
		{1, 4},
		{3, 4},
		{3, 5},

	}


	sg := new(sparseGraph)

	n := data[0][0]
	sg.init(n, true)

	for i := 1; i < n; i++ {

		sg.addEdge(data[i][0], data[i][1]);
	}

	//rand.Seed(time.Now().Unix())
	//
	//for i := 0; i < n; i++ {
	//	a := rand.Intn(100) % n
	//	b := rand.Intn(100) % n
	//	dg.addEdge(a, b);
	//}

	sg.show()

	//fmt.Println(dg.getComponentCount())

	//sg.initPath(0)
	//fmt.Println(from)

	//sg.showPath(6)

}
